#ifndef YFWZ100_FUNDAMENTAL_HASHMAP_HPP
#define YFWZ100_FUNDAMENTAL_HASHMAP_HPP

#include "common.hpp"

YFWZ100_FUNDAMENTAL_NS_BEGIN

template <typename K>
struct Hasher
{
  virtual size_t operator()(const K &key) = 0;
};

template <>
struct Hasher<int>
{
  virtual size_t operator()(const int &key)
  {
    return key;
  }
};

template <>
struct Hasher<float>
{
  virtual size_t operator()(const int &key)
  {
    return (size_t)key;
  }
};

template <>
struct Hasher<double>
{
  virtual size_t operator()(const int &key)
  {
    return (size_t)key;
  }
};

template <>
struct Hasher<short>
{
  virtual size_t operator()(const int &key)
  {
    return (size_t)key;
  }
};

template <typename K, typename V,
          typename H = Hasher<K>>
class HashMap
{
protected:
  // the entry type.
  struct Entry
  {
    K key;
    V val;
    Entry(K key) : key(key) {}
    Entry(K key, V val) : key(key), val(val) {}
  };
  typedef Entry *EntryPointer;

  void resize(size_t new_size)
  {
    // temporary original data.
    auto old_back = _back;
    auto old_capacity = _capacity;
    // construct the new structure.
    _capacity = new_size;
    _back = new EntryPointer[new_size];
    _size = 0;
    // initialize the null pointer.
    for (int i=0; i<_capacity; ++i)
    {
      _back[i] = nullptr;
    }
    // restore the old data.
    for (int i = 0; i < old_capacity; ++i)
    {
      if (old_back[i] != nullptr)
      {
        auto e = old_back[i];
        insert(e->key, e->val);
        delete e;
      }
    }
  }

private:
  // back data storage.
  EntryPointer *_back;
  // attributes.
  size_t _size;
  size_t _capacity;
  float _enlarge_factor;
  // accessory functions.
  H _hash;

public:
  HashMap(size_t capacity = 16,
          float enlarge_factor = 0.75) : _back(new EntryPointer[capacity]),
                                         _size(0),
                                         _enlarge_factor(enlarge_factor),
                                         _capacity(capacity)
  {
    for (int i = 0; i < capacity; ++i)
    {
      _back[i] = nullptr;
    }
  }

  virtual ~HashMap()
  {
    clear();
    delete[] _back;
  }

  void clear()
  {
    // release the space occupied by keys and values.
    for (int i = 0; i < _capacity; ++i)
    {
      if (_back[i] != nullptr)
      {
        delete _back[i];
        _back[i] = nullptr;
      }
    }
    _size = 0;
  }

  bool contains(const K &key) const
  {
    size_t idx = _hash(key);
    if (_back[idx] == nullptr)
    {
      return false;
    }
    else if (_back[idx]->key == key)
    {
      return true;
    }
    else
    {
      size_t i = idx + 1;
      while (i != idx && _back[i] != nullptr)
      {
        if (_back[i]->key == key)
        {
          return true;
        }
        i = (i + 1) % _capacity;
      }
      return false;
    }
  }

  bool is_empty()
  {
    return _size == 0;
  }

  void insert(const K &key, const V &val)
  {
    size_t idx = _hash(key) % _capacity;
    if (_back[idx] == nullptr)
    {
      _back[idx] = new Entry(key, val);
      _size += 1;
    }
    else if (_back[idx]->key == key)
    {
      _back[idx]->val = val;
    }
    else
    {
      size_t i = (idx + 1) % _capacity;
      while (i != idx && _back[i] != nullptr)
      {
        if (_back[i]->key == key)
        {
          break;
        }
        i = (i + 1) % _capacity;
      }
      if (i == idx)
      {
        // no enough space so we have to resize.
        size_t new_size = _size + (size_t) (_size * _enlarge_factor);
        resize(new_size);
        // recursive call to insert key value pair.
        this->insert(key, val);
      }
      else if (_back[i] == nullptr)
      {
        _back[i] = new Entry(key, val);
        _size += 1;
      }
      else
      {
        _back[i]->val = val;
      }
    }
  }

  V &operator[](const K &key)
  {
    size_t idx = _hash(key) % _capacity;
    if (_back[idx] == nullptr)
    {
      _back[idx] = new Entry(key);
      _size += 1;
      return _back[idx]->val;
    }
    else if (_back[idx]->key == key)
    {
      return _back[idx]->val;
    }
    else
    {
      size_t i = (idx + 1) % _capacity;
      while (i != idx && _back[i] != nullptr)
      {
        if (_back[i]->key == key)
        {
          break;
        }
        i = (i + 1) % _capacity;
      }
      if (i == idx)
      {
        // no enough space so we have to resize.
        size_t new_size = _size + (size_t) (_size * _enlarge_factor);
        resize(new_size);
        // recursive call to get value by key.
        return this->operator [](key);
      }
      else
      {
        if (_back[i] == nullptr)
        {
          _back[i] = new Entry(key);
          _size += 1;
        }
        return _back[i]->val;
      }
    }
  }

  size_t size()
  {
    return _size;
  }

  size_t capacity()
  {
    return _capacity;
  }
};

YFWZ100_FUNDAMENTAL_NS_END

#endif //YFWZ100_FUNDAMENTAL_HASHMAP_HPP